UVa/11848 - Cargo Trains/11848.cpp

   1 // Accepted
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 typedef pair<int, long long> edge; // first = weight, second = node
  29
  30 const int MAXN = 105;
  31
  32 vector< edge > ga[MAXN], gb[MAXN];
  33
  34 long long g[MAXN][MAXN][2];
  35
  36 double d[MAXN];
  37
  38 int shortestPath(int start, int end, double percentage, int N) {
  39     for (int i = 0; i < N; ++i) {
  40         d[i] = 1e200;
  41     }
  42
  43     d[start] = 0.0;
  44     priority_queue < pair< double, int >, vector< pair<double, int> >, greater< pair<double, int> > > q;
  45     q.push(  make_pair(0.0, start) );
  46
  47     while (q.size() > 0) {
  48         int u = q.top().second;
  49         double w = q.top().first;
  50         q.pop();
  51
  52         if (w > d[u]) continue;
  53         if (u == end) return floor(w);
  54
  55         for (int v = 0; v < N; ++v) {
  56             if (g[u][v][0] == -1 and g[u][v][1] == -1) continue;
  57
  58             double extra;
  59             if (g[u][v][0] != -1 and g[v][u][1] != -1) {
  60                 extra = percentage * g[u][v][0] + (1.0 - percentage) * g[u][v][1];
  61             } else {
  62                 extra = max(g[u][v][0], g[u][v][1]);
  63             }
  64             if (w + extra < d[v]) {
  65                 d[v] = w + extra;
  66                 q.push( make_pair(w + extra, v) );
  67             }
  68         }
  69     }
  70     assert(false);
  71 }
  72
  73
  74 int main(){
  75
  76     //printf("2.9 = %d 2.1 = %d, 2.999999999999999999999 = %d, 2.5 = %d, 2.0 = %d\n", (int)2.9, (int)2.1, (int)2.999999999999999999999, (int)2.5, (int)2.0);
  77
  78     int numCities, numEdgesA, numEdgesB, combinations;
  79     while (cin >> numCities >> numEdgesA >> numEdgesB >> combinations) {
  80         if (numCities == -1 and numEdgesA == -1 and numEdgesB == -1 and combinations == -1) break;
  81         /*the number of cities, the number of edges in the network of company A,
  82         the number of edges in the network of company B,
  83         and the number of combination alternatives respectively.
  84         */
  85         for (int i = 0; i < numCities; ++i) {
  86             for (int j = 0; j < numCities; ++j) {
  87                 g[i][j][0] = g[i][j][1] = -1;
  88             }
  89         }
  90         for (int k = 0; k < numEdgesA; ++k) {
  91             int u, v; long long w;
  92             cin >> u >> v >> w;
  93             assert(g[u][v][0] == -1 and g[v][u][0] == -1);
  94             g[u][v][0] = w;
  95             g[v][u][0] = w;
  96         }
  97         for (int k = 0; k < numEdgesB; ++k) {
  98             int u, v; long long w;
  99             cin >> u >> v >> w;
 100             assert(g[u][v][1] == -1 and g[v][u][1] == -1);
 101             g[u][v][1] = w;
 102             g[v][u][1] = w;
 103         }
 104
 105         for (int k = 0; k < combinations; ++k) {
 106             double c;
 107             cin >> c;
 108             cout << shortestPath(0, numCities - 1, c, numCities) << endl;
 109         }
 110     }
 111
 112
 113     return 0;
 114 }